package com.interview.javabasic.Sort;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0,13,15,2,6};
        shellSort(arr);

    }
    public static void shellSort(int arr[]){
        int tmp = 0;
        int count = 0;
        //希尔排序的第一轮排序
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap;i<arr.length;i++){
                //遍历各组元素，j-=5，步长是5
                for (int j=i-gap;j>=0;j-=gap){
                    //如果当前元素大于后面的元素，需要交换
                    if (arr[j] > arr[j+gap]){
                        tmp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = tmp;
                    }
                }
            }
            System.out.println("第"+(++count)+"次希尔排序："+Arrays.toString(arr));
        }

    }

    //优化 交换->移动法
    public static void shellSort2(int arr[]){
        int count = 0;
        //希尔排序的第一轮排序
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap;i<arr.length;i++){
               int j = i;
               int tmp = arr[j];
               if (arr[j] < arr[j - gap]){
                   while (j-gap>=0 && tmp < arr[j - gap]){
                       arr[j] = arr[j-gap];
                       j -= gap;
                   }
                   //退出循环后，就找到了插入的位置。
                   arr[j] = tmp ;
               }
            }
            System.out.println("第"+(++count)+"次希尔排序："+Arrays.toString(arr));
        }
    }
}
